﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithms
{

    /// <summary>
    /// 返回指定目标数索引之和
    /// https://leetcode.com/problems/two-sum/description/
    /// </summary>
    public class TwoSum
    {
        #region 两次for循环的暴力方法
        public static int[] Action1(int[] nums, int target)
        {
            int[] num = new int[2];
            for (int i = 0; i < nums.Length; i++)
            {
                for (int j = 0; j < i; j++)
                {
                    if (nums[i] + nums[j] == target)
                    {
                        num[0] = j;
                        num[1] = i;
                        break;
                    }
                }
                if (num[0] != 0)
                {
                    break;
                }

            }
            return num;
        }

        #endregion

        #region 使用哈希表
        public static int[] Action2(int[] nums, int target)
        {
            int[] ret = new int[2];     //返回的数组

            Dictionary<int, int> dic = new Dictionary<int, int>();
            for (int k = 0; k < nums.Length; k++)
            {
                if (dic.ContainsKey(nums[k]))
                {
                    continue;
                }
                dic.Add(nums[k], k);
            }

            for (int k = 0; k < nums.Length; k++)
            {
                if (dic.ContainsKey(target - nums[k]) == true)
                {
                    int a = dic[target - nums[k]];
                    if (a < k)
                    {
                        ret[0] = a;
                        ret[1] = k;
                    }
                    else
                        if (a > k)
                    {
                        ret[0] = k;
                        ret[1] = a;
                    }
                    else
                    {
                        continue;
                    }

                    break;
                }
            }
            return ret;
        }
        #endregion
    }
}
